1. Field of Invention
The field of this patent is in the area of forward error correction and its applications.
2. Description of Related Art
All information transmission protocols are block structured.
Block structured block codes are standardized for error detection and re-transmission.
Block codes, particular short code lengths, are scarce and less powerful.
convolutional codes are known to produce a large number of optimal block codes
All Internet transmission relies on a set of transmission protocols.
All Internet transmission protocols rely on error detection and re-transmission, or error detection without re-transmission
The Internet Transmission Protocols
For transmission, the key mechanism of the Internet is the following set major protocols:
TCP (Transmission Control Protocol),
(Internet Protocol),
ICMP (Internet Control Message Protocol),
IGMP (Internet Group Management Protocol),
PPP (Point to Point Protocol)
FTP, TFTP (Trivial File Transfer Protocol),
UDP (User Datagram Protocol),
IMP (Internet Multicast Protocol),
Under ICMP, there exists transmission protocols for address, timestamp request and reply, router solicitation, router advertisement, Echo request and reply, timing exceeded messages, redirected messages, and unreachable messages. Each transmission protocol has its unique format and structure, and they have been specified by the IETF as standards. Each of these protocols contains the provision of either Checksum, or ARU, or CRC for error detection and/or re-transmission.
Error Detection and/or Re-transmission
For error protection, telecommunication industry depends on error detection and re-transmission. All present and planned Internet transmission schemes rely on either error detection or re-transmission, or no error detection but waiting for delayed non-response time. The error detection and re-transmission techniques have been referred to as automatic repeat request (ARQ). The delayed response and re-transmission schemes have been referred to as the Windowed method. The Window size, specified by the IETF (Internet Engineering Task Force) and practiced by all the ISPs (Internet Service Providers), is related to the amount of delay time allowed.
All ARQ use error codes without forward correction capability. These ARQ codes are selected, internationally standardized, and called CRC (Cyclic Redundancy Checks). The generator polynomials of the CRC codes are:                                                                         g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    4                                    )                                            =                              xe2x80x83                            ⁢                              1                +                x                +                                  x                  2                                +                                  x                  3                                +                                  x                  4                                                                                                                        g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    7                                    )                                            =                              xe2x80x83                            ⁢                              1                +                                  x                  4                                +                                  x                  6                                +                                  x                  7                                                                                                                        g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    8                                    )                                            =                              xe2x80x83                            ⁢                                                (                                      1                    +                    x                                    )                                ⁢                                  (                                      1                    +                    x                    +                                          x                      2                                                        )                                ⁢                                  (                                      1                    +                                          x                      2                                        +                                          x                      3                                        +                                          x                      4                                        +                                          x                      5                                                        )                                                                                                                        g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    12                                    )                                            =                              xe2x80x83                            ⁢                              1                +                x                +                                  x                  2                                +                                  x                  3                                +                                  x                  11                                +                                  x                  12                                                                                                                        g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    16                    ⁢                    a                                    )                                            =                              xe2x80x83                            ⁢                              1                +                                  x                  2                                +                                  x                  15                                +                                  x                  16                                                                                                                        g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    16                    ⁢                    b                                    )                                            =                              xe2x80x83                            ⁢                              1                +                                  x                  5                                +                                  x                  12                                +                                  x                  16                                                                                                                        g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    16                    ⁢                    c                                    )                                            =                              xe2x80x83                            ⁢                              1                +                x                +                                  x                  2                                +                                  x                  4                                +                                  x                  7                                +                                  x                  13                                +                                  x                  15                                +                                  x                  16                                                                                                                        g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    24                                    )                                            =                              xe2x80x83                            ⁢                              1                +                                  x                  8                                +                                  x                  12                                +                                  x                  14                                +                                  x                  23                                +                                  x                  24                                                                                                                        g                ⁡                                  (                                      CRC                    ⁢                                          -                                        ⁢                    32                                    )                                            =                              xe2x80x83                            ⁢                              1                +                x                +                                  x                  2                                +                                  x                  4                                +                                  x                  5                                +                                  x                  7                                +                                  x                  8                                +                                  x                  10                                +                                  x                  11                                +                                                                                                        xe2x80x83                            ⁢                                                x                  12                                +                                  x                  16                                +                                  x                  23                                                                                        (        1        )            
The CRC-16a has been standardized by ANSI. The CRC-16b has been standardized by the ITU-T and widely used worldwide. The CRC-16c has been standardized for SDLC. For CRC-32 there exist two more versions depending on the applications. For the Internet transmission, some protocols have specified one or more of the above CRCs. But most Internet Transmission Protocols rely on the structure of Checksums for error protection as to be described next.
The Checksum Computations
Based on ordinary arithmetic computations in computers the technique of Checksum was developed based on arithmetic coding. In this case, the numbers are represented by a set of polynomials in a radix system. For every such number, there is a unique binary representation in terms of the powers of the radix=2 and coefficients +1, xe2x88x921, or 0. To encode a number n, multiply n by a factor of the radix r, then add a value b. That is, the coded form is c=nr+b. To decode, the decoder first subtract b from c, then divide by r. If the division produces a nonzero remainder, an error is detected. The condition here requires that n is relatively prime to r.
Presently, the Internet uses 16-bit bytes in its Checksum portion of all the transmission protocol formation. The Checksum function is the one""s complement sum. That is, additions are performed with arithmetic carry on the bytes. It is the one""s complement of this sum that is stored in all the protocols, which contains Checksums. For Checksums the radix base r is chosen to be 216. This way, every 16-bit byte is considered as a digit of a number, and this number is the message.
The implementation of the Internet Checksum is the result of conversion of the division computation to addition. This is based on the following identity valid for r=216 xe2x88x921 and any digit D in radix r:
D*rj=Dmod(rxe2x88x921)xe2x80x83xe2x80x83(2)
In the statement, any digit D in radix r multiply any power of the radix will have a remainder D when divided by the radix minus one. Thus, the remainder of a number divided by the radix minus one can be obtained by adding the digits of the number. Thus the required division process becomes addition operation and the decoding in Checksum becomes summing all the 16-bit words with carries. As a result, errors can be detected after the summation procedure.
The Checksum operation is described as:
Two adjacent 8-bit symbols are pair-wise checksum to form 16-bit integers.
The 1""s complement sum of these 16-bit integers is then formed.
The 16-bit 1""s complement sum is computed over the set of message symbols.
The 1""s complement of this sum is the 16-bit Checksum for encoding.
To perform error detection, the 1""s complement sum is computed over the same set of message symbols.
If the computed result is all 1""s, (xe2x88x920 in 1""s complement arithmetic) check is completed.
Limitations and Problems
The severity of limitation and problem depends on the application, client""s demand, server""s availability, and network condition, at that time. In most cases, limitations and problems are separately treated and improvements are separately sought.
Network and Throughput Problems
The Internet network operators are using load balancing algorithms, scheduling techniques, renaming network elements, rotating servers, and user message behavior in order to optimize the network utilization. These algorithms and procedures require constant monitoring and updating. As a consequence, the operations not only become complicated and costly, but also decrease the network throughput.
Bandwidth and Congestion Problems
As the Internet traffic increases, congestion is expected, and bandwidth has been recognized as scarce commodity. In addition to loading balancing and message sensing methods, advance service such as Differential Service technique and its variation have been proposed in order to conserve bandwidth. But these techniques cause delay and create uncertainty and undesirability from a client""s viewpoint.
Efficiency and Reliability Problems
Transmission protocols are the backbones of the Internet. There are four basic layers in protocol internetworking architecture: the Application Layer, the Transport Layer, the Inter-network Layer, and the Network Interface Layer. The last one is also called data link layer, which provides interface to the networks such as ATM, FDDI. The IP is the heart of the Inter-network Layer, which does not provide any measure of link reliability. The only error protection mechanism in the IP is a very simple error detection scheme for the protection of the Header.
At the receiving end, if an error is detected in the IP Header, the entire Header and the corresponding message are discarded. There is no provision for re-transmission request. Even in the absence of heavy user traffic, different time delay has been experienced when Internet is logged-on. This is due to either noise or interference in the transmission channel, and the IP keeps discarding the Header to prevent information with error.
There are three types of ARQ: Stop and Wait, Go Back-N, and Select Repeat. A transmission protocol assigns sequence numbers to each transmitted data block, and expects a positive acknowledgment from the Transport Layer from a receiver. If an acknowledgment is not received in a timely manner, the entire block is re-transmitted. This re-transmission protocol is a variation of the Select Repeat -ARQ. When a transmission channel is noisy, all transmission schemes based on ARQ become inefficient.
Presently, the Internet, based on the protocols, has not been able to provide high reliability and efficiency. If a feedback channel is available, repeated transmission decreases efficiency. If a feedback channel is not available, one takes a chance at the receiving end. For some transmission in real time, such as voice and video, and errors occur, it is not always feasible to stop in the middle and request for re-transmission.
Compatibility and Standards Problems
Standardization affects not only users, but also equipment manufacturers, and network operators. In the telecom industry, no matter how innovative the technology, how wonderful the product and how low the price, if it cannot be standardized, it cannot sell even if it is a bad standard. A product becomes marketable only when it can comply, with multiple existing standards.
Wireless standards come from IEEE 802.11 and are limited to physical layer and the common medium access control of wireless LAN. For the wireless Internet, the Internet Engineering Task Force (WETF) is working toward establishing standards for mobile internetworking through Internet Protocol version 6 (IPv6).
Delay and Speed Problems
One of the Next Generation Internet (NGI) goals is to increase the present Internet speed by a thousand fold. Most work in this area concerns with the speed of the devices and modems. None has investigated the delay and slow speed caused by re-transmission.
The problems and limitations are not limited to the Internet transmission. They are common to all information transmissions. As results of the above discussions, needs exist to overcome the limitations and problems in order to conserve bandwidth, reduce redundant traffic, enhance efficiency, minimize message delay, improve reliability, ameliorate transmission capacity, and increase transmission speed.
This invention invents, derives, constructs forward error correction codes and designs, selects, evaluates, and tests the codecs (encoders/decoders). The invention either fully or partially eliminates all re-transmission schemes and replaces them with forward error corrections without replacing any standardized signaling formats.
This invention advances the state-of-the-art of optimally converting any convolutional code with any of its decoding methods to block structured block code.
As an example, this invention addresses the key elements of the Internetxe2x80x94the network transmission aspects of the Internet inner workings. The attributes, the impact, and the utilization of the invention are identified through the following seven attributes, which are achievable with single solution approach of this invention. The invention significantly impacts on:
Bandwidth conservation
Traffic congestion
Efficiency enhancement
Message delay reduction
Reliability improvement
Transmission channel capacity amelioration
Transmission speed increase
No other single solution is known capable of achieving all seven attributes simultaneously. No other solution is known to obtain each of the attributes effectively.
What make this invention different from others include:
Innovation
Beyond existing coding theories, this invention converts any convolutional code to a block code.
The invention provides ARQs, CRCs, and Checksums replacements by means of forward error-correcting codes.
The invention achieves in deriving new codes, modifying known codes, and selecting existing codes to meet all the requirements of the Internet transmission protocols.
Uniqueness
The invention produces simultaneously the following attributes in any information transmission: channel capacity amelioration, bandwidth conservation, throughput enhancement, reliability improvement, increase transmission speed, message delay reduction, and prevent traffic congestion.
The invention constructs unique test configuration with programmable error generation, and statistical error analyses.
Merit
The solutions advanced in this invention meet all the segmentation requirements of all the standardized Internet Transmission Protocols without a single bit alteration.
The approaches advanced in this invention are useful not limited to Internet.